package com.coder.algorithm.offer_2;

import java.util.Arrays;

/**
 * 数组中只出现一次的两个数字
 *
 * @author yuhushuan
 * @date 2020/6/30 22:00
 */
public class _56_1_NumbersAppearOnce {
    private static void findNumbersAppearOnce(int[] data) {
        if (data == null || data.length < 2) {
            System.out.println("null");
            return;
        }

        int resultExclusiveOR = 0;
        for (int i = 0; i < data.length; ++i) {
            resultExclusiveOR ^= data[i];
        }

        int indexOf1 = findFirstBitIs1(resultExclusiveOR);
        int number1 = 0, number2 = 0;
        for (int number : data) {
            if (isBit1(number, indexOf1)) {
                number1 ^= number;
            } else {
                number2 ^= number;
            }
        }
        System.out.println(Arrays.toString(new int[]{number1, number2}));
    }

    private static int findFirstBitIs1(int number) {
        int indexBit = 0;
        while ((number & 1) == 0 && indexBit < 32) {
            indexBit++;
            number = number >> 1;
        }
        return indexBit;
    }

    private static boolean isBit1(int number, int indexBit) {
        number = number >> indexBit;
        return (number & 1) == 1;
    }

    public static void main(String[] args) {
        // 存在多对重复数字
        print(new int[]{2, 4, 3, 6, 3, 2, 5, 5});
        // 没有重复的数字
        print(new int[]{1, 2, 3, 4, 5});
    }

    private static void print(int[] data) {
        System.out.println("数组：" + Arrays.toString(data));
        System.out.println("只出现一次的两个数字：");
        findNumbersAppearOnce(data);
        System.out.println();
    }
}
